Image segmentation is the problem of extracting or “segmenting” objects of interest from non-interesting background information in an image. Reliable image segmentation algorithms are required in many fields, particularly for medical images such as CT (computerized tomography) scans, MRI (magnetic resonance imaging) scans, PET (positron emission tomography) scans and the like. For the field of medical image processing, it is important to be able to accurately, rapidly and reliably perform segmentation, as medical diagnoses increasingly rely upon such information.
Fully automatic image segmentation has so far proven to be impractical and unreliable, particularly for three dimensional images such as those which arise from the above described scans. These three dimensional images are provided as a series of two dimensional slices. Image segmentation algorithms must therefore relate to both individual two dimensional slices and to the overall three dimensional construct that is composed of a plurality of such slices. Many of the currently available medical image processing algorithms rely upon a mixture of automated and manual algorithms, which require human interaction with the medical image data.
Interactive image segmentation has therefore become more and more popular among users of medical image data processing software. Many of these semi-automatic tools are prone to errors that require some form of user interaction for correcting them. Such user interaction is often cumbersome, requiring tedious and lengthy operations by the user.
There are two basic types of graph-based segmentation algorithms, which may be used for such interactive image segmentation, including for both medical and non-medical image data: (1) implicit boundary algorithms and (2) explicit boundary algorithms. Implicit boundary algorithms, such as graph cuts or normalized cuts, label each node (pixel) as foreground (i.e., of interest) or background (i.e., not of interest) and imply the boundary between them by the labeling. In contrast, explicit boundary algorithms, such as “livewire” or “intelligent scissors”, identify the boundary explicitly and implicitly define a foreground/background labeling.
The livewire method was originally described in a paper by Mortensen and Barret, entitled “Intelligent Scissors for Image Composition” (Computer Graphics Proceedings, Annual Conference Series, 1995, which is hereby incorporated by reference as if fully set forth herein) and balances the benefits of manual intervention with the advantages provided by computer generated boundary points. During intelligent scissors segmentation, a seed point is placed on a boundary edge of a selected object in the image through a manual input of the user to the user interface of software operating according to the intelligent scissors algorithm. During normal operations, the user moves a pointing device along a boundary of the object adding seed points at various locations. As the user continues to move the pointing device, a “live wire” boundary line is established, which is the result of the method, attempting to follow or “snap to” the boundary of the object.
The livewire method relies on Dijkstra's graph search algorithm to find the lowest cost path between a start node, given as the previously placed seed point, and all other nodes in a weighted graph. Specifically, the complete image is represented as a graph with each pixel representing a node and edges representing the connection between one pixel and each of its eight neighboring pixels. The cost of an edge may optionally be calculated so that edges with strong gradients have a lower cost, causing the algorithm to seek or “snap to” strong gradients. On each move of the mouse (or the pointing device), the method seeks the lowest cost path from the previous seed point to the current mouse position. Dijkstra's algorithm is described in Cormen, Leiserson and Rivest, “Introduction to Algorithms”, McGraw-Hill.
Once the user places a new seed point, the livewire path from the previous seed point to the new seed point is “frozen” and a new livewire path is now drawn from the newly placed seed point to the current mouse or other pointing device position. As a result, a line, also referred to as a “live wire”, is generated and wraps the object by following paths back to the original seed point. The concatenation of the lowest-cost paths between every pair of consecutive placed seed points is the resulting livewire path that wraps the object. Thus, boundary edges are mathematically determined using dynamic programming based on minimal energy comparison techniques.
Many commercially available software programs for image processing of three dimensional medical image data use some variation of the intelligent scissors/live wire algorithm for image segmentation (also known as the “lasso” algorithm). However, since the live wire algorithm is only able to operate in two dimensions, relying solely on this algorithm would mean that in order to fully segment a 3D object the user would have to draw a live wire line on each and every slice belonging to the object. Such an operation is cumbersome and slow so methods have been devised that allow a user to draw contours on a select number of slices and have the remaining slices interpolated over. The interpolation process may not necessarily be a straightforward linear interpolation, but may in fact be a more complex algorithmic procedure taking into account the actual image data. An example of such an algorithmic process may involve the livewire algorithm itself or some deformable contour model.
Some examples of references that relate to continuing a contour line through multiple slices (although not necessarily with livewire) include U.S. Pat. No. 7,668,349 and US2009/0274350, which describe different methods for interpolating such slices. U.S. Pat. No. 7,668,349 allows the user to indicate the correct model shape by drawing a contour on a displayed image of the segmented object of interest, and then to require the system to make the model follow this contour through a plurality of two dimensional slices, after which a three dimensional model may be generated.
US2009/0274350 is directed to image segmentation in generating computer models of a joint by obtaining a plurality of volumetric image slices of the bone and generating a plurality of spline curves associated with the bone. A three dimensional representation of the bone is then generated based upon the spline curve.
The common link to all such algorithms is that they allow the segmentation of objects from scratch. However, many times an automatic, or semi-automatic, tool will be used in order to segment a 3D object and upon review of this object, errors in the segmentation are seen. The previously described programs are not suited for doing error corrections of pre-segmented data.